/**
 * 给定数组A，对每个Ai，要么加入B，要么加入C
 * 要求最后任意bi与cj，gcd为1。
 * 筛出质数，然后利用并查集将Ai根据质因子分到对应的地方
 * 最后再检查一下即可
 */
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

template<typename T>
void input(vector<T> & v, int n){
	v.assign(n + 1, {});
	for(int i=1;i<=n;++i) cin >> v[i];
	return;
}

struct Sieve{ // 线性筛法

using llt = long long;
vector<bool> isComp; // isComp[i]表示i是否为合数
vector<llt> primes; // primes[i]是第i个质数


Sieve(int SZ = 1100){
    primes.reserve(SZ);
    isComp.assign(SZ, false);    

    long long tmp;
    for(int i=2;i<SZ;++i){
        if(!isComp[i]){
            primes.push_back(i);
        }

        for(int j=0,n=primes.size();j<n&&(tmp=i*(long long)primes[j])<SZ;++j){
            isComp[tmp] = true;

            if(0 == i % primes[j]){
                break;
            }else{
            }
        }
    }
}

}Sie;

using Real = long double;
using llt = long long;
using vi = vector<int>;
using pii = pair<int, int>;

struct uf_t{
unordered_map<int, int> father;

void init(){father.clear();}

int find(int x){
    auto it = father.find(x);
    if(it == father.end()){
        it = father.insert(it, {x, x});
        return it->second;
    }
    if(it->second == x) return x;
    return it->second = find(it->second);
}
void unite(int x,int y){father[find(y)]=find(x);}

}UF;

int const LEVEL = 1000000;

int N;
vector<int> A, B, C;

bool hasOne(){
    bool flag = false;
    for(int i=1;i<=N;++i)if(1==A[i]){flag=true;break;}
    if(not flag) return false;

    B.clear(); C.clear();
    for(int i=1;i<=N;++i){
        if(1==A[i] and B.empty()) B.emplace_back(1);
        else C.emplace_back(A[i]);
    }
	cout << B.size() << " " << C.size() << "\n";
	for(auto i : B) cout << i << " "; cout << "\n";
	for(auto i : C) cout << i << " "; cout << "\n";    
    return true;
}

void work(){
    cin >> N;
	input(A, N);

    if(hasOne()) return;

	UF.init();
	for(int i=1;i<=N;++i){
		auto a = A[i];
		for(auto p : Sie.primes){
            if(0 == a % p){
				UF.unite(A[i], p + LEVEL);
				while(0 == a % p) a /= p;
			}
			if(p * p > a) break;
		}
		if(a != 1) UF.unite(A[i], a + LEVEL);
	}

	B.clear(); C.clear();
	int t1 = UF.find(A[1]);
	for(int i=1;i<=N;++i){
		if(t1 == UF.find(A[i])) B.emplace_back(A[i]);
		else C.emplace_back(A[i]);
	}

	if(C.empty()) return (void)(cout << "-1 -1\n");
	cout << B.size() << " " << C.size() << "\n";
	for(auto i : B) cout << i << " "; cout << "\n";
	for(auto i : C) cout << i << " "; cout << "\n";
	return;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    B.reserve(100000); C.reserve(100000);
	int nofkase = 1;
    cin >> nofkase;
    while(nofkase--) work();
    return 0;
}